/*
 * @Author: your name
 * @Date: 2021-10-17 12:37:18
 * @LastEditTime: 2021-10-17 19:54:09
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \luogu\动态规划\背包\完全背包\P2722 总分 Score Inflation\main.cpp
 */
#include<iostream>
#include<algorithm>
using namespace std;

//f[i] 花费i时间获得的最大分数
int f[10010];

//ff[i][j] 对于前i道题 花费j时间 获得的最大分值ff
int ff[10010][10010];

int main(){
    int m,n;
    cin >> m >> n;
    for(int i=1; i<=n; i++){
        int p,t;
        cin >> p >> t;
        for(int j=t; j<=m; j++){
            f[j] = max(f[j],f[j-t]+p);
        }

        for(int j=0; j<=m; j++){
            //对比对象为当下
            //写不完 分值不变
            if(j < t){
                ff[i][j] = ff[i-1][j];
            }else{
                //写得完
                ff[i][j] = max(ff[i-1][j],ff[i][j-t]+p);
            }
        }
    }
    cout << f[m] << endl;
    cout << ff[n][m] << endl;
    return 0;
}
